package leetcode.primary;

public class T72 {
    public int minDistance(String word1, String word2) {
        if (word1==null || word2==null){
            return 0;
        }
        int len1 = word1.length();
        int len2 = word2.length();
        if (len1*len2==0){
            return len1+len2;
        }

        int[] dp = new int[len2+1];
        for (int i = 0; i <=len2; i++) {
            dp[i] = i;
            System.out.print(dp[i]+" ");
        }
        System.out.println();

        int diagonal=0;
        int upper;
        int left;
        for (int i = 1; i <=len1; i++) {
            for (int j = 0; j <=len2; j++) {
                if (j==0){
                    diagonal = dp[j];
                    dp[j] = i;
                    System.out.print(dp[j]+" ");
                    continue;
                }
                 upper = dp[j];
                 left = dp[j-1];
                if (word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[j] = diagonal;
                }else {
                    dp[j] = Min(upper,left,diagonal)+1;
                }
                diagonal = upper;
                System.out.print(dp[j]+" ");
            }
            System.out.println();
        }
        return dp[len2];

    }
    public int Min(int a,int b,int c){
        return  Math.min(Math.min(a,b),c);
    }

    public static void main(String[] args) {
        T72 test = new T72();
        int minDistance = test.minDistance("kitten", "sitting");
        System.out.println(minDistance);
    }
}
